#!/usr/bin/python



#empty spaces + stone colors
BLANK=0
BLACK=1
WHITE=2
#used to determine the relationship between connected stones
UNRELATED=3
FRIENDS=4
ENEMIES=5
#Used to announce which player is making a move.
COLOR_STRINGS = {BLANK:"Blank", WHITE:"White", BLACK:"Black"}

class IllegalMoveException(Exception):
	"""Raised when an illegal move by the rules of Go is made."""
	def __init__(self, coordinates, reason):
		"""Create a new IllegalMoveException where the move occured at
		coordinates and the move is illegal because of reason."""
		self.coordinates = coordinates
		self.reason = reason

class BoardReadException(Exception):
	"""Raised when a problem occurred with loading the board from a file."""
	pass

class GoBoard(object):
	"""Represents a board for a Go game."""
	size = int()
	board = [] #two-dimensional
	previous_state = [] #two-dimensional, used to check for Ko
	vocal = bool() 	#used to determine whether the board should announce 
					#each move that is made

	def __init__(self, size=19, src_file=None, vocal=False):
		"""Make a new size*size Go board with handicap stones preset in black's
		favor. Reads in board state from the open readable .gdb file src_file
		if provided. src_file must be at the beginning of the line where the
		board state starts and must conform to the .gdb specification(see 
		GDB-README.txt) or a BoardReadException will be raised."""
		#TODO: handle handicaps. Currently nothing is done.
		self.size = size
		self.vocal = vocal
		if src_file:
			self.read_board(src_file)
		else:
			#set board to all empty squares
			for i in range(0, size):
				self.board.append([])
				for j in range(0, size):
					self.board[i].append(BLANK)
	
	def __str__(self):
		"""Displays the board."""
		result = ""
		for row in self.board:
			for stone in row:
				if stone == BLANK:
					result += "- "
				elif stone == BLACK:
					result += "b "
				elif stone == WHITE:
					result += "w "
				else:
					result += "? "
			result += "\n"
		return result	

	def read_board(self, src_file):
		"""Reads in a board from the open readable .gdb file src_file. 
		src_file must be at the beginning of the line where the
		board state starts and must conform to the .gdb specification(see 
		GDB-README.txt) or a BoardReadException will be raised."""
		for i in range(0, self.size):
			self.board.append([]) #add a new row
			line = src_file.readline()
			if not line:
				raise BoardReadException("Board ended too soon at line %d. \
					Did you forget a line of stones in your .gbd file?" % i+1)
			else:
				for j in range(0, self.size):
					stone = line[j]
					if stone == '-':
						self.board[i].append(BLANK)
					elif stone == 'b':
						self.board[i].append(BLACK)
					elif stone == 'w':
						self.board[i].append(WHITE)
					else:
						raise BoardReadException("Illegal board character %s \
							at line %d, column %d. Character should be one of \
							'-', 'b', or 'w'." % (stone, i+1, j+1))

	def make_move(self, color, coordinates):
		"""Makes a move for color at coordinates. If the move is illegal, raises
		an IllegalMoveException."""
		#if the spot is already taken, it's illegal
		if self.in_bounds(coordinates) and not self.taken(coordinates): 
			#make sure it's not being put in a surrounded area
			if not self.surrounded(coordinates):
				#move is legal, announce
				if self.vocal: 
					print("%s makes a move at row %d, column %d" % \
						(COLOR_STRINGS.get(color), coordinates[0]+1, \
						coordinates[1]+1))
				self.previous_state = list(self.board)
				self.set_color(coordinates, color)
				for stone in self.adjacent(coordinates):
					if self.get_relationship(coordinates, stone) == ENEMIES \
						and self.surrounded(stone): 
						print("You surrounded another stone at %s" % str(stone))
						self.remove(stone)
			else:
				#even though the stone is surrounded, is it surrounding another
				#group of stones? If so then legal and other stones should be
				#removed(unless resetting board to same state as before last 
				#move(Ko rule), then illegal)
				surrounding_others = False
				
				#backup the current and previous states in case Ko applies
				old_state = list(self.previous_state)
				self.previous_state = list(self.board)

				#now let's place the stone
				self.set_color(coordinates, color)
				if self.vocal: print("%s makes a move at row %d, column %d" % \
					(COLOR_STRINGS.get(color), coordinates[0]+1, coordinates[1]+1))
				for stone in self.adjacent(coordinates):
					if self.surrounded(stone):
						print("you are surrounded but so is another stone")
						surrounding_others = True
						
						num_removed = self.remove(stone)
						#Check for Ko. Only applies when one stone has been
						#removed.
						if num_removed == 1:
							if old_state == self.board:
								#whoops! Ko rule applies. This is illegal, 
								#revert the board and raise exception.
								self.board = list(self.previous_state)
								self.previous_state = list(old_board)
								raise IllegalMoveException, coordinates
				if not surrounding_others:
					self.set_color(coordinates, BLANK)
					reason = "Placed stone into surrounded area without removing \
any surrounding stones."
					raise IllegalMoveException(coordinates, reason)
		else:
			if not self.in_bounds(coordinates): 
				reason = "Coordinates outside of board boundaries."
			else:
				reason = "Postion has already been taken by another stone."
			raise IllegalMoveException(coordinates, reason)

	def has_liberties(self, coordinates):
		"""Checks to see if the position at coordinates has any liberties
		remaining; that is, if it has any blank spaces in the adjacent
		squares. Returns True if yes, False otherwise."""
		adjacent = self.adjacent(coordinates)
		return len([stone for stone in adjacent if not self.taken(stone)]) != 0

	def surrounded(self, coordinates, explored=[]):
		"""Checks if the group of same-colored stones connected to the stone at 
		coordinates is surrounded by stones of the opposite color. Doesn't
		check connected stones in explored. Returns true if yes, false 
		otherwise."""
		color = self.get_color(coordinates)
		explored.append(coordinates)
		#check that it has no liberties and that each connected stone
		#in the same group is also surrounded.
		if self.has_liberties(coordinates):
			return False
		else:
			friendly_stones = [stone for stone in self.adjacent(coordinates) \
				if self.get_relationship(coordinates, stone) == FRIENDS]
			print friendly_stones
			if not friendly_stones:
				return True
			else:
				print("We have friendly stones")
				explored.append(coordinates)
				for stone in friendly_stones:
					print("Testing friendly stones")
					if stone not in explored:
						print("Testing %s" % str(stone))
						if not self.surrounded(stone, explored):
							print("Success! Not surrounded!")
							return False

				return True

	def get_color(self, coordinates):
		"""Returns the color of the stone at coordinates."""
		return self.board[coordinates[0]][coordinates[1]]
	
	def set_color(self, coordinates, color):
		"""Sets the position at coordinates to color."""
		self.board[coordinates[0]][coordinates[1]] = color

	def adjacent(self, coordinates):
		"""Returns all the adjacent positions to coordinates that are within
		the boundaries of the board."""
		adjacent = [(coordinates[0]-1, coordinates[1]),
					(coordinates[0], coordinates[1]-1),
					(coordinates[0]+1, coordinates[1]),
					(coordinates[0], coordinates[1]+1)]
		return [position for position in adjacent if self.in_bounds(position)]

	def in_bounds(self, coordinates):
		"""Returns True if coordinates is within the boundaries of the board,
		False otherwise."""
		return ((coordinates[0] >= 0 and coordinates[0] < self.size) and
			(coordinates[1] >= 0 and coordinates[1] < self.size))

	def remove(self, coordinates):
		"""Removes the group of same colored stones connected to the stone at
		coordinates. Returns the amount of stones removed."""
		num_removed = 1
		color = self.get_color(coordinates)
		connected = [stone for stone in self.adjacent(coordinates) 
			if self.get_color(stone) == color]
		self.board[coordinates[0]][coordinates[1]] = BLANK
		for stone in connected:
			num_removed += self.remove(stone)
		return num_removed
	
	def taken(self, coordinates):
		"""Returns True if the position at coordinates is taken by another 
		stone, False otherwise."""
		return self.get_color(coordinates) != BLANK
		
	def get_relationship(self, stone1, stone2):
		"""Checks if the two stones located at coord1 and coord2 are the
		opposite color. Returns True if yes, False otherwise."""
		color1 = self.get_color(stone1)
		color2 = self.get_color(stone2)
		#make sure that there are stones in these squares
		if color1 and color2:
			return FRIENDS if color1 == color2 else ENEMIES
		else:
			#a blank square can't be an enemy or a friend
			return UNRELATED

if __name__ == "__main__":
	board = GoBoard(size=5, vocal=True)
	board.board = [[WHITE, BLACK, WHITE, BLANK, BLANK],
					[BLACK, BLACK, BLACK, BLANK, BLANK],
					[WHITE, BLACK, WHITE, BLANK, BLANK],
					[BLANK, WHITE, BLANK, BLANK, BLANK],
					[BLANK, BLANK, BLANK, BLANK, BLANK]]
	print board
	board.make_move(WHITE, (1, 3))
	print board
